package leetcode.editor.cn;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname DifferentialArray
 * @description [370] 区间加法
 * @date 2023/03/23 14:32
 * <p>
 * ******************************************************
 */
public class DifferentialArray {
    /**
     * 例如nums:[8,5,9,6,1]
     * 那么diff:[8,-3,4,-3,-5]
     * 原数组可通过diff推导出来：num[0]=diff[0] \  num[1]=diff[0]+diff[1] \ num[2] = num[1] + diff[2]  \ ......
     * 假设[1, 3]加3，那么只需diff[1]+3，diff[4]-3
     */
    private int[] diff;

    /* 输入一个初始数组，区间操作将在这个数组上进行 */
    public DifferentialArray(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        diff[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i, j] 增加 val（可以是负数）*/
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    /* 返回结果数组 */
    public int[] result() {
        int[] result = new int[diff.length];
        result[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }


    /**
     * 假设你有一个长度为 n的数组，初始情况下所有的数字均为 0，你将会被给出k 个更新的操作
     * 其中，每个操作会被表示为一个三元组: [startlndex,endindex,inc]，你需要将子数组A[startIndex ...endIndex] (包括startlndex 和 endlndex) 增加inc。请你返回k 次操作后的数组
     * 示例:
     * 输入: length = 5，updates = [[1,3,2],[2,4,3],[0,2,-2]]输出: [-2,0,3,5,3]
     * 解释
     * 初始状态:
     * [0,0,0,0,0]
     * 进行了操作 [1,3,2] 后的状态:[0,2,2,2,0]
     * 进行了操作 [2,4,3] 后的状态:[0,2,5,5,3]
     * 进行了操作 [0,2,2] 后的状态:[-2,0,3,5,3]
     *
     * @param length
     * @param updates
     * @return
     */
    public int[] getModifiedArray(int length, int[][] updates) {
        // nums 初始化为全 0
        int[] nums = new int[length];
        // 构造差分解法
        DifferentialArray differentialArray = new DifferentialArray(nums);
        for (int i = 0; i < updates.length; i++) {
            differentialArray.increment(updates[i][0], updates[i][1], updates[i][2]);
        }
        return differentialArray.result();
    }


    /**
     * 这里有n个航班，它们分别从 1到n进行编号
     * 我们这儿有一份航班预订表，表中第i条预订记录 bookings[i] = [，j，k] 意味着我们在从到的每个航班上预订了k个座位。
     * 请你返回一个长度为n的数组 answer，按航班编号顺序返回每个航班上预订的座位数
     * 示例:
     * 输入: bookings = [[1,2,10],[2,3,20],[2,5,25]]，n = 5输出: [10,55,45,25,25]
     *
     * @param bookings
     * @param n
     * @return
     */
    public int[] corpFlightBookings(int[][] bookings, int n) {
        // nums 初始化为全 0
        int[] nums = new int[n];
        // 构造差分解法
        DifferentialArray differentialArray = new DifferentialArray(nums);
        for (int i = 0; i < bookings.length; i++) {
            // 因为题意是下标是从1开始
            differentialArray.increment(bookings[i][0] - 1, bookings[i][1] - 1, bookings[i][2]);
        }
        return differentialArray.result();
    }

    /**
     *
     * 车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
     *
     * 给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
     *
     * 当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
     *
     *
     *
     * 示例 1：
     *
     * 输入：trips = [[2,1,5],[3,3,7]], capacity = 4
     * 输出：false
     * 示例 2：
     *
     * 输入：trips = [[2,1,5],[3,3,7]], capacity = 5
     * 输出：true
     *
     * 1 <= trips.length <= 1000
     * trips[i].length == 3
     * 1 <= numPassengersi <= 100
     * 0 <= fromi < toi <= 1000
     * 1 <= capacity <= 105
     *
     * @param trips
     * @param capacity
     * @return
     */
    public boolean carPooling(int[][] trips, int capacity) {
        // nums 初始化为全 0
        // 从0 <= fromi < toi <= 1000得知，最多有1001站
        int[] nums = new int[1001];
        // 构造差分解法
        DifferentialArray differentialArray = new DifferentialArray(nums);
        for (int i = 0; i < trips.length; i++) {
            // 第 trip[i][2] 站乘客已经下车，
            // 即乘客在车上的区间是 [trip[i][1], trip[i][2] - 1]
            differentialArray.increment(trips[i][1], trips[i][2] - 1, trips[i][0]);
        }
        int[] res = differentialArray.result();

                 // 客车自始至终都不应该超载
        for (int i = 0; i < res.length; i++) {
            if (capacity < res[i]) {
                return false;
            }
        }
        return true;
    }

}
